package sjjg.graph;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

public class BrodeFirstSearch {
    private boolean[]marked;//下标代表某个节点 用来表示某个节点是否被搜索过
    private int count;//用来记录与传入节点相通的节点个数
    private LinkedBlockingDeque<Integer>queue;//辅助完成广度优先搜索 类似于层序遍历
    BrodeFirstSearch(Graph graph, int v){
        marked=new boolean[graph.V()];
        queue=new LinkedBlockingDeque<>();
        count=0;
        bfs(graph,v);
    }
    private void bfs(Graph graph,int v){
            queue.add(v);
            while (!queue.isEmpty()){
                Integer pop = queue.pop();
                count++;
                marked[pop]=true;
                for (Integer integer : graph.adj[pop]) {
                     if(!marked[integer]){
                         queue.add(integer);
                     }
                }
            }
    }
    public boolean marked(int w){//判断w与v是否相通
           return marked[w];
    }
    public int getCount(){//反回与v相通的节点数
        return count;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.addEdge(0,1);
        graph.addEdge(1,5);
        graph.addEdge(5,3);
        graph.addEdge(3,2);
        graph.addEdge(2,4);
        graph.addEdge(6,7);
        graph.addEdge(8,8);
        BrodeFirstSearch depthFirstSearch = new BrodeFirstSearch(graph, 0);
        //返回与0相通的节点个数
        int count = depthFirstSearch.getCount();
        System.out.println("与0相通的节点个数为："+count);
        //判断5与0是否相通
        boolean marked5 = depthFirstSearch.marked(5);
        System.out.println("5与0相通"+marked5);
        //判断7与0是否相通
        boolean marked7 = depthFirstSearch.marked(7);
        System.out.println("7与0相通"+marked7);

    }
}
